#
# @lc app=leetcode.cn id=77 lang=python3
#
# [77] 组合
#

# @lc code=start


class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        """回溯法"""
        # 判特殊
        if n <= 0 or k <= 0 or k > n:
            return []
        res = []
        self._backtrack(1, k, n, [], res)
        return res

    def _backtrack(self, start, k, n, pre, res):
        """
        start:搜索起点
        k: 层数
        n: 树的宽度
        pre: 已选路径
        res: 结果
        """
        # 出口：第k层
        if k == len(pre):
            res.append(pre[:])
            return
        for i in range(start, n + 1):
            # 做选择
            pre.append(i)
            # 已经把 i 加入到 pre 中，下一轮就从 i + 1 开始
            self._backtrack(i + 1, k, n, pre, res)
            # 回溯时，状态重置
            pre.pop()

        # @lc code=end
